package board;

import list.ArrayList;

//import test.Printer;

public class DepthFirstSearch {

	/**
	 * If player_color has a winning network, it will return true. Else, if
	 * there is no winning network, returns false.
	 * 
	 * @param color
	 *            the player you wish to check.
	 * @param b
	 *            the board to check on.
	 * @return
	 */
	public static ArrayList<Piece> hasWin(int color, Board b) {
		if (color == Piece.BLACK) {
			for (int x = 1; x <= 6; x++) { // search black's home row
				Piece p = b.pieceAt(x, 0);
				if (p.isEmpty())
					continue; // skip empty tiles
				ArrayList<Piece> win = depthFirstSearch(b, p, UNDIRECTED, 1,
						new ArrayList<Piece>(), false, false);
				if (win != null)
					return win;
			}
		} else if (color == Piece.WHITE) {
			for (int y = 1; y <= 6; y++) { // search white's home row
				Piece p = b.pieceAt(0, y);
				if (p.isEmpty())
					continue; // skip empty tiles
				ArrayList<Piece> win = depthFirstSearch(b, p, UNDIRECTED, 1,
						new ArrayList<Piece>(), false, false);
				if (win != null)
					return win;
			}
		}
		return null;
	}

	public static final int winningLength = 6;
	static final int N = 1;
	static final int NE = 2;
	static final int E = 3;
	static final int SE = 4;
	static final int S = 5;
	static final int SW = 6;
	static final int W = 7;
	static final int NW = 8;
	static final int UNDIRECTED = -1;

	/**
	 * Returns the winning network or null if none is found.
	 * 
	 * @param currentpiece
	 * @param direction
	 * @param networkCount
	 * @return
	 */
	private static ArrayList<Piece> depthFirstSearch(Board b,
			Piece currentpiece, int direction, int networkCount,
			ArrayList<Piece> usedPieces, boolean homeRowUsed,
			boolean goalRowUsed) {

		usedPieces.add(currentpiece);
		if (currentpiece.goalRow()) {
			if (goalRowUsed)
				return null;
			else {
				goalRowUsed = true;
			}
		}
		if (currentpiece.homeRow()) {
			if (homeRowUsed)
				return null;
			else
				homeRowUsed = true;
		}

		if (networkCount == winningLength) { // check for wins
			if (currentpiece.goalRow()) { // check if it is on black goal row
				return usedPieces;
			}
		}
		int opp_direction = (direction + 4) % 8;
		if (direction == UNDIRECTED){
			opp_direction = UNDIRECTED;
		}
		for (int i = 1; i <= 8; i++) {// loop through all directions
			if (i == direction || i == opp_direction)
				continue;

			Piece connectedPiece = getConnectedPiece(b, currentpiece, i);

			if (usedPieces.contains(connectedPiece)) {
				// do nothing
			} else if (connectedPiece == null) {
				// do nothing
			}
			else {
				ArrayList<Piece> winNetwork = depthFirstSearch(b,
						connectedPiece, i, networkCount + 1,
						(ArrayList<Piece>) usedPieces.clone(), homeRowUsed,
						goalRowUsed);
				if (winNetwork != null) {
					return winNetwork;
				}
			}
		}
		
		//No more connections! All connections exhausted
		if(evaluating)
			notifyEndNetwork(usedPieces); //eval needs to count ended networks
		return null;
	}

	/**
	 * Returns the first piece same-color piece found while traveling in the given direction
	 * <br>
	 * Returns null if connection is blocked or no connection is found
	 * 
	 * @param xpos
	 * @param ypos
	 * @param xcolor
	 * @param direction
	 * @return
	 */
	private static Piece getConnectedPiece(Board b, Piece p, int direction) {
		int[] moveVector = getMoveVector(direction);
		int xpos = p.xpos + moveVector[0];
		int ypos = p.ypos + moveVector[1];
		while (isInBounds(xpos, ypos, p.color)) {
			Piece newPiece = b.pieceAt(xpos, ypos);
			if (newPiece.isEmpty()) { // empty tile found. checking next tile
				xpos = xpos + moveVector[0];
				ypos = ypos + moveVector[1];
				continue;
			} else if (newPiece.color == p.color) { // connection found!
				return newPiece;
			} else { // the piece is opposite color
				return null;
			}
		}
		return null;
	}

	/**
	 * Chekcs if coordinates <x,y> are in bounds
	 * @param x
	 * @param y
	 * @param color
	 * @return
	 */
	private static boolean isInBounds(int x, int y, int color) {
		if (x > 7 || x < 0 || y > 7 || y < 0) {
			return false;
		}
		if (color == Piece.BLACK) { 		// check if it is on home rows
			if (x == 7 || x == 0)
				return false;
		}
		if (color == Piece.WHITE) {
			if (y == 7 || y == 0)
				return false;
		}
		// check if it is one of the four corners
		if ((x == 0 && y == 0) || (x == 7 && y == 0) || (x == 0 && y == 7)
				|| (x == 7 && y == 7))
			return false;
		return true;
	}

	/**
	 * Returns a vector corresponding to the given direction.
	 * <br>
	 * Ex, 
	 * <br>
	 * NORTH = <0,-1>
	 * <br>
	 * SOUTH = <0,1>
	 * <br>
	 * NORTHWEST = <-1,-1>
	 * @param direction
	 * @return a 2-element array, where element0 is movement along x-axis and element1 is y-axis
	 */
	private static int[] getMoveVector(int direction) {
		int[] moveVector = { 0, 0 }; // x,y
		if (direction == N || direction == NW || direction == NE) {
			moveVector[1] = -1;
		} else if (direction == S || direction == SW || direction == SE) {
			moveVector[1] = 1;
		}
		if (direction == W || direction == NW || direction == SW) {
			moveVector[0] = -1;
		} else if (direction == E || direction == NE || direction == SE) {
			moveVector[0] = 1;
		}
		if (moveVector[0] == 0 && moveVector[0] == moveVector[1]) {
			throw new RuntimeException("Invalid direction: " + direction);
		}
		return moveVector;
	}

	/* ********************
	 * 
	 * BELOW IS FOR EVAL - RELATED METHODS
	 * 
	 * *******************
	 */
	private static ArrayList<Integer> lengths;
	private static boolean evaluating;
	
	/**
	 * Returns a list containing a list of the lengths of all networks (not
	 * necessarily winning) owned by a player. <br>
	 * Used for eval purposes; more networks = more winning.
	 * 
	 * @param b
	 * @param color
	 * @return
	 */
	public static ArrayList<Integer> getNetworkLengths(Board b, int color) {
		evaluating = true;
		lengths = new ArrayList<Integer>();
		ArrayList<Piece> coloredPieces = null;
		if (color == Piece.BLACK) {
			coloredPieces = b.blackPieces;
		} else if (color == Piece.WHITE) {
			coloredPieces = b.whitePieces;
		}
		for (int i = 0; i < coloredPieces.size(); i++) {
			depthFirstSearch(b, coloredPieces.get(i), UNDIRECTED, 0,
					new ArrayList<Piece>(), false, false);
		}
		evaluating = false;
		return lengths;
	}
	
	private static void notifyEndNetwork(ArrayList<Piece> network) {
		lengths.add(network.size());
	}
	/*
	private static void depthFirstSearch2(Board b, Piece currentpiece,
			int direction, int networkCount, ArrayList<Piece> usedPieces,
			boolean homeRowUsed, boolean goalRowUsed) {
		// Printer.println("Current piece: "+currentpiece
		// +" used: "+usedPieces+" networkLen: "+networkCount);
		// Printer.tab();
		usedPieces.add(currentpiece);

		if (currentpiece.goalRow()) {
			if (goalRowUsed) {
				notifyEndNetwork(usedPieces);
				return;
			} else {
				goalRowUsed = true;
			}
		}
		if (currentpiece.homeRow()) {
			if (homeRowUsed) {
				notifyEndNetwork(usedPieces);
				return;
			} else
				homeRowUsed = true;
		}

		int opp_direction = (direction + 4) % 8;
		if (direction == UNDIRECTED)
			opp_direction = UNDIRECTED;

		for (int i = 1; i <= 8; i++) {// loop through all directions
			if (i == direction || i == opp_direction)
				continue;
			Piece connectedPiece = getConnectedPiece(b, currentpiece, i);
			if (usedPieces.contains(connectedPiece)) {
				// Printer.println("Piece alread used!");
				// do nothing
			} else if (connectedPiece == null) {
				// do nothing
			} else {
				depthFirstSearch2(b, connectedPiece, i, networkCount + 1,
						(ArrayList<Piece>) usedPieces.clone(), homeRowUsed,
						goalRowUsed);
			}
		}
		// Printer.untab();
		// Printer.println("\t "+currentpiece+" has no more connections!");
		notifyEndNetwork(usedPieces);
	}
	*/

}
